package backtracking;

import java.util.ArrayList;
import java.util.List;

/**
 * 131.分割回文串
 * 给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
 */
public class partition {
    /**
     * 一刷二刷都需注意
     */
    //保持前几题一贯的格式， initialization
    List<List<String>> res = new ArrayList<>();
    List<String> cur = new ArrayList<>();

    public List<List<String>> partition(String s) {
        backtracking(s, 0, new StringBuilder());
        return res;
    }

    private void backtracking(String s, int start, StringBuilder sb) {
        //因为是起始位置一个一个加的，所以结束时start一定等于s.length,因为进入backtracking时一定末尾也是回文，所以cur是满足条件的
        if (start == s.length()) {
            //注意创建一个新的copy
            res.add(new ArrayList<>(cur));
            return;
        }
        //像前两题一样从前往后搜索，如果发现回文，进入backtracking,起始位置后移一位，循环结束照例移除cur的末位
        for (int i = start; i < s.length(); i++) {
            sb.append(s.charAt(i));
            if (check(sb)) {
                //只有是回文子串才加入到cur中,不是回文直接跳过。
                // 假如第一个是回文，后面的不是回文，第一个是回文会进入递归，那么后面的不是回文不会递归，只会append，在append后会走到第一个回文添加的时候 cur.add(sb.toString());然后回remove
                cur.add(sb.toString());
                backtracking(s, i + 1, new StringBuilder());
                cur.remove(cur.size() - 1);
            }
        }
    }

    //helper method, 检查是否是回文
    private boolean check(StringBuilder sb) {
        for (int i = 0; i < sb.length() / 2; i++) {
            if (sb.charAt(i) != sb.charAt(sb.length() - 1 - i)) {
                return false;
            }
        }
        return true;
    }

}

/**
 * hot100一刷
 * hot100二刷
 */
class S {
    List<List<String>> res = new ArrayList<>();
    List<String> path = new ArrayList<>();

    public List<List<String>> partition(String s) {
        StringBuffer sb = new StringBuffer();
        backtracking(s, 0, new StringBuffer());
        return res;
    }

    public void backtracking(String s, int start, StringBuffer sb) {
        if (start == s.length()) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = start; i < s.length(); i++) {
            sb.append(s.charAt(i));
            if (isvalid(sb.toString())) {
                path.add(sb.toString());
                backtracking(s, i + 1, new StringBuffer());
                path.remove(path.size() - 1);
            }
        }
    }

    public boolean isvalid(String s) {
        if (s.length() == 1)
            return true;
        int l = 0;
        int r = s.length() - 1;
        while (l <= r) {
            if (s.charAt(l) != s.charAt(r)) {
                return false;
            }
            l++;
            r--;
        }
        return true;
    }
}


